Specious rules: an efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining

摘要

We present theoretical analysis and a suite of tests and procedures foraddressing a broad class of redundant and misleading association rules we call\emph{specious rules}. Specious dependencies, also known as \emph{spurious},\emph{apparent}, or \emph{illusory associations}, refer to a well-knownphenomenon where marginal dependencies are merely products of interactions withother variables and disappear when conditioned on those variables. The most extreme example is Yule-Simpson's paradox where two variablespresent positive dependence in the marginal contingency table but negative inall partial tables defined by different levels of a confounding factor. It isaccepted wisdom that in data of any nontrivial dimensionality it is infeasibleto control for all of the exponentially many possible confounds of this nature.In this paper, we consider the problem of specious dependencies in the contextof statistical association rule mining. We define specious rules and show theyoffer a unifying framework which covers many types of previously proposedredundant or misleading association rules. After theoretical analysis, weintroduce practical algorithms for detecting and pruning out speciousassociation rules efficiently under many key goodness measures, includingmutual information and exact hypergeometric probabilities. We demonstrate thatthe procedure greatly reduces the number of associations discovered, providingan elegant and effective solution to the problem of association miningdiscovering large numbers of misleading and redundant rules.